#ifndef BINARYHEAP_H
#define BINARYHEAP_H

#include "Item.h"
#include "RuntimeException.h"

//I prefer not to use this class, but time was short...
template <typename T>
class PQComp{
public:
	int operator() (const Item<T>& e1, const Item<T>& e2){
		return e1.get_key() - e2.get_key();
	}
};

template <typename T, typename C>
class BinaryHeap{
private:
	C comp;
	int cur_size;
	T *array;
	int length;
	static const int DEF_SIZE = 8;
	void get_new_array(int new_size){
		
		if (!empty()){
			T *temp = array;
			int t_length = length;
		
			array = new T[new_size];
			length = new_size;
		
			for (int i = 0; i < t_length; i++)
			{
				array[i] = temp[i];
			}
			
			delete[] temp;
			return;
		}
		
		array = new T[new_size];
		length = new_size;
	}
	
	int cmps;
public:
	struct EmptyHeap : public RuntimeException {
		EmptyHeap() : RuntimeException("Heap is Empty") {}
	};
	
	BinaryHeap(int size = DEF_SIZE){
		cur_size = 0;
		//cmps = 0;
		get_new_array(size);
	}
	~BinaryHeap(){ delete[] array; }
	
	T& find_min() throw(EmptyHeap){
		if (empty()) throw EmptyHeap();
		return array[0];
	}
	
	bool empty() const { return cur_size == 0; }
	
	void check_size(){
		if (cur_size == length) get_new_array(length*2);
	}
	
	void insert(const T& x, int& num_cmps);
	void delete_min(int& num_cmps) throw(EmptyHeap);
	void walk_up(const T& x, int hole, int& num_cmps);
	void walk_down(int hole, int& num_cmps);
	
	int get_cmps(){ return cmps; }
	int size(){ return cur_size; }
	
	template <typename F>
	friend class HPQueue;
};

template <typename T, typename C>
void BinaryHeap<T, C>::insert (const T& x, int& num_cmps){
	check_size();

	array[cur_size] = x;
	*(array[cur_size].pos) = cur_size;

	walk_up(x, cur_size, num_cmps); //I think the problem exists here
	/*for ( ; hole > 0 && comp(array[(hole-1)/2], x) > 0; hole = (hole-1)/2)
		array[hole] = array[hole(-1)/2];
	array[hole] = x;*/
	
	cur_size++;
}

template <typename T, typename C>
void BinaryHeap<T,C>::delete_min(int& num_cmps) throw(EmptyHeap){
	array[0] = array[ --cur_size ];
	walk_down(0,num_cmps);
}

template <typename T, typename C>
void BinaryHeap<T,C>::walk_up(const T& x, int hole, int& num_cmps){
	for ( ; hole > 0 && (num_cmps++, comp(array[(hole-1)/2], x) > 0); hole = (hole-1)/2){
		array[hole] = array[(hole-1)/2];
		*(array[hole].pos) = hole;
	}
	array[hole] = x;
	*(array[hole].pos) = hole;
}

template <typename T, typename C>
void BinaryHeap<T,C>::walk_down(int hole, int& num_cmps)
{
	int child; T key = array[hole];
	for ( ; 2*hole+1 < cur_size; hole = child){
		child = 2*hole+1;
		num_cmps+=2;
		if (child != cur_size-1 && comp(array[child], array[child+1]) > 0)
			child++;
		if(comp(key, array[child]) > 0){
			array[hole] = array[child];
			*(array[hole].pos) = hole; //check
		}
		else break;
	}
	array[hole] = key;
	*(array[hole].pos) = hole;
}
#endif
